package first.bishiti;

/**
 * @ClassName bapackage
 * @description:
 * @author: 荣燊
 * @create: 2021-06-17 21:59
 **/
public class Bpackage {
    public static void main(String[] args) {
        int target = 5;
        int[] weights = {1, 2, 3};
        int[] values = {6, 10 ,12};

//        Scanner scanner = new Scanner(System.in);
//        int target = scanner.nextLine();
//        String[] wei = scanner.nextLine().split(",");
//        String[] val = scanner.nextLine().split(",");
//        int[] weights = new int[wei.length];
//        int[] values = new int[val.length];
//        for (int i=0; i<wei.length; i++) {
//            weights[i] = Integer.parseInt(wei[i]);
//            values[i] = Integer.parseInt(val[i]);
//        }
        System.out.println(maxPackage(target, weights, values));
    }

    public static int maxPackage(int target, int[] weights, int[] values) {
        int[][] dp = new int[weights.length+1][target + 1];

        // 可以不用置0，初始即为0
//        for (int i=0; i<weights.length; i++) {
//            dp[i][0] = 0;
//        }

        for (int i=1; i<weights.length+1; i++) {
            for (int j=1; j<target+1; j++) {
                if (j >= weights[i-1]) {
                    // dp[i][j]表示只放入前i个物品时，最大不超过j的重量的，最大值
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[weights.length-1][target];
    }

    /**
     * dp[i][j] = max{dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1]}
     * dp[i-1][j]：减少 本次添加物品 的最大重量
     * dp[i-1][j-w[i-1]] ：减少 本次添加物品 且剩余的重量为j-w[i-1]，w[i-1]就是本次物品的重量
     */
}
